#include <vector>
#include <queue>

using std::vector;
using std::queue;
using std::pair;

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        queue<pair<int, int>> q;
        int m = board.size();
        int n = board[0].size();
        int** arr = new int* [m];
        for (int i = 0; i < m; i++) {
            arr[i] = new int[n];
            for (int j = 0; j < n; j++) {
                arr[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O' && arr[0][i] == 0) {
                check(board, q, arr, 0, i);
            }
            if (board[m - 1][i] == 'O' && arr[m - 1][i] == 0) {
                check(board, q, arr, m - 1, i);
            }
        }
        for (int i = 1; i < m - 1; i++) {
            if (board[i][0] == 'O' && arr[i][0] == 0) {
                check(board, q, arr, i, 0);
            }
            if (board[i][n - 1] == 'O' && arr[i][n - 1] == 0) {
                check(board, q, arr, i, n - 1);
            }
        }
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (arr[i][j] == 0 && board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
        for (int i = 0; i < m; i++) {
            delete[] arr[i];
        }
        delete[] arr;
    }

    void check(vector<vector<char>>& board, queue<pair<int, int>>& q, int** arr, int x, int y) {
        arr[x][y] = 1;
        q.emplace(x, y);
        while (!q.empty()) {
            int a = q.front().first;
            int b = q.front().second;
            q.pop();
            if (a > 0 && board[a - 1][b] == 'O' && arr[a - 1][b] == 0) {
                arr[a - 1][b] = 1;
                q.emplace(a - 1, b);
            }
            if (a < board.size() - 1 && board[a + 1][b] == 'O' && arr[a + 1][b] == 0) {
                arr[a + 1][b] = 1;
                q.emplace(a + 1, b);
            }
            if (b > 0 && board[a][b - 1] == 'O' && arr[a][b - 1] == 0) {
                arr[a][b - 1] = 1;
                q.emplace(a, b - 1);
            }
            if (b < board[0].size() - 1 && board[a][b + 1] == 'O' && arr[a][b + 1] == 0) {
                arr[a][b + 1] = 1;
                q.emplace(a, b + 1);
            }
        }
    }
};